﻿/*
H 二叉树路径和II
分数 40
作者 朱允刚
单位 吉林大学
编写程序找出非空二叉树中和最大的路径，二叉树结点为不等于0的整数。本题的“路径”定义为二叉树中的结点序列v
i
​
 ,...,v
j
​
 ，序列中前一个结点是后一个结点的父结点，但路径不一定是以根结点为起点，也不一定是以叶结点为终点。路径的和定义为该路径所包含的所有结点的数据值之和。

输入格式:
输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。

输出格式:
输出为两行，第一行为该二叉树路径和的最大值，第二行为一组整数，每个整数后一个空格，表示该最大路径包含的结点值（按所在层数递增顺序输出）。如果存在多条满足条件的路径，则输出最短（包含结点个数最少）者，如果存在多条最短的路径，则输出最靠左上者。

输入样例1:
1 2 0 0 3 0 0

输出样例1:
4
1 3

输入样例2:
-1 2 0 0 3 4 0 0 0

输出样例2:
7
3 4

输入样例3:
3 2 0 0 -1 4 0 0 0

输出样例3:
6
3 -1 4

代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB
*/

#include <iostream>
#include <vector>

using namespace std;

// 定义二叉树结点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 结果存储结构体
struct Result {
    int sum;
    vector<int> path;
};

// 计算最大路径和
Result maxPathSum(TreeNode* root) {
    Result result;

    if (!root) {
        result.sum = 0;
        return result;
    }

    // 计算左子树和右子树的最大路径和
    Result leftResult = maxPathSum(root->left);
    Result rightResult = maxPathSum(root->right);

    // 计算以当前结点为根的路径和
    int currentSum = root->val + max(0, leftResult.sum) + max(0, rightResult.sum);

    // 更新最大路径和和路径
    if (currentSum > result.sum) {
        result.sum = currentSum;
        result.path.clear();
        result.path.push_back(root->val);
        for (int val : leftResult.path) {
            result.path.push_back(val);
        }
        for (int val : rightResult.path) {
            result.path.push_back(val);
        }
    }

    // 返回以当前结点为根的最大路径和
    return { root->val + max(0, max(leftResult.sum, rightResult.sum)), {root->val} };
}

int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->right = new TreeNode(-1);
    root->left->left = nullptr;
    root->left->right = nullptr;
    root->right->left = new TreeNode(4);
    root->right->right = nullptr;

    // 计算最大路径和
    Result result = maxPathSum(root);

    // 输出结果
    cout << result.sum << endl;
    for (int val : result.path) {
        cout << val << " ";
    }
    cout << endl;

    // 释放内存
    delete root->left;
    delete root->right->left;
    delete root->right;
    delete root;

    return 0;
}
